package gold.digger;

import gold.utils.InputUtil;

import java.util.ArrayList;
import java.util.List;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC792 {
    public long startExecuteTime = System.currentTimeMillis();


    class Solution {
        public int numMatchingSubseq(String s, String[] words) {
            int[][] dp = new int[s.length()][26];  //dp[i][j]表示s在位置i，对于字母j，下一个最近的位置下标
            for (int i = s.length() - 1; i >= 0; i--) {
                for (int j = 0; j < 26; j++) {
                    if (i == s.length() - 1) dp[i][j] = -1;
                    else if (j == s.charAt(i + 1) - 'a') dp[i][j] = i + 1;
                    else dp[i][j] = dp[i + 1][j];
                }
            }

            int matchCount = 0;
            for (String word : words) {
                int curMatchPos = 0;
                boolean curMatchResult = true;
                for (char c : word.toCharArray()) {
                    if (curMatchPos > s.length() - 1) {
                        curMatchResult = false;
                        break;
                    }

                    if (s.charAt(curMatchPos) == c) {
                        ++curMatchPos;
                        continue;
                    }

                    int nextPos = dp[curMatchPos][c - 'a'];
                    if (-1 == nextPos) {
                        curMatchResult = false;
                        break;
                    }

                    curMatchPos = nextPos + 1;
                }

                if (curMatchResult) ++matchCount;
            }

            return matchCount;
        }
    }


    public void run() {
        Solution solution = new Solution();
        String s = "iwdlcxpyagegrcnrcylxolxlnhhwnxyzltiscrjztiivnpnzlubzpueihinsqdfvypdteztiodbhaqhxskupwulvkzhczdyoouym";
        String[] arr = {"hhwnxyzltiscrjztiivnpnzlubzpueihinsqdfvyp", "vnpnzlubzpueihinsqdfvypdteztiodbha", "rcnrcylxolxlnhhwnxyzltiscrjztiivnpnzlubzpueihi", "dfvypdteztiodbhaqhxskupwulvk", "zltiscrjztii", "wdmbatbcewwittubryrqwwrvfkrmniomofygybeqfzusrgeart", "myzfexqmzxnbmmnhmpbddqhrwrobqzjiwdzzpyzodejysuuquc", "wxvrcbihbasohfvuwuxleesqeujxvjfvgwnhltenbspdgzsdrs", "nztyysfhfbfcihyeaqdarqxfpjunevabzafvbmpbtenarvyizv", "nivufheyodfjuggrbndyojeahrzgptikjfqufhwyhzyyjteahx"};
        System.out.println(solution.numMatchingSubseq(s, arr));
    }

    public static void main(String[] args) throws Exception {
        LC792 an = new LC792();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
